
//1931.检查网格中是否存在有效路径
class Solution {
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        //使用一个数组来记录每个图片的来源对应的出处
        int pipe[][4]={
            {},
            {-1,-1,3,2},
            {1,0,-1,-1},
            {-1,2,1,-1},
            {-1,3,-1,1},
            {2,-1,0,-1},
            {3,-1,0,-1}
        };
        int dx[]={-1,1,0,0};  //将上下左右对应的x和y的增长情况存储起来
        int dy[]={0,0,-1,1};
        int n=grid.size(),m=grid[0].size();
        vector<vector<int>> vist(n,vector<int>(m,-1));
        function<bool(int,int,int)> dfs=[&](int x,int y,int dir)
        {
            if(vist[x][y]==1) return false;
            vist[x][y]=1;
            int next=pipe[grid[x][y]][dir],now=0;  //从那个方向到下一个位置
            if(next==-1) return false;

            if(next==0) now=1;     //now存储该位置在下一个位置的哪个方向,即与next相反,确定下一个位置的来源
            else if(next==1) now=0;
            else if(next==2) now=3;
            else now=2;
            
            if(x==n-1&&y==m-1) return true;
            int a=x+dx[next],b=y+dy[next];          //下一个位置的坐标
            if(a<0||a>=n||b<0||b>=m) return false;
            return dfs(a,b,now);
        };

        for(int i=0;i<4;i++)
        {
            vist=vector<vector<int>>(n,vector<int>(m,-1));   //记忆化存储,让已经走过的地方不再走,防止死循环
            if(dfs(0,0,i)) return true;    //第一个位置向线下左右四个方向都试一遍
        }
        return false;
    }
};